import sun.security.provider.MD2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-02
 * Time: 22:42
 */
public class Solution {
    private boolean postOrder(int [] sequence, int begin, int end){
        if(begin >= end){
            return true;
        }
        int value = sequence[end];
        // 注意这里面是将 下标赋值给了 mid, 而不是对应的值
        int mid = begin;
        // 找到左右子树的分界, 这里注意 mid < end , 不能等于 end
        while (mid < end && sequence[mid] < value){
            mid++;
        }
        // 如果右子树中仍然有节点 < sequence[end], 说明不是后序遍历
        int i = mid;
        while (i < end){
            // 这里面应该注意是与 value 比较, 而不要写成下标
            if(sequence[i] <= value){
                return false;
            }
            i++;
        }
        // sequence[mid] > value                                这里注意 end 下标已经不能再参与右子树了
        return postOrder(sequence, begin, mid - 1) && postOrder(sequence, mid, end - 1);
    }
    public boolean VerifySequenceOfBST(int [] sequence) {
        int length = sequence.length;
        if(length == 0){
            return false;
        }
        return postOrder(sequence, 0, length - 1);
    }
}
